package 排序算法.选择排序;

import java.util.Arrays;

/**
 * @Project: data-structure-and-algorithms
 * @Package: 排序.选择排序
 * @ClassName: SelectionSort
 * @Author: zhouyihe
 * @Date: 2025/11/12 17:23
 * @Description: 选择排序
 */
public class SelectionSort {

    /**
     * 选择排序
     * 优点：
     * 实现简单，思路清晰
     * 交换操作的次数比冒泡排序少，平均性能比冒泡排序好
     * 对于小规模的数据效率还算可以
     * 不占用额外内存空间
     * 缺点：
     * 时间复杂度固定为 O(n²) ，无论输入数据如何都要扫描全部未处理的元素
     * 不稳定的排序算法，可能会改变相同元素的相对位置
     * 当数据量较大时，效率低下
     * @param arr
     */
    public static void selectionSort(int[] arr) {
        for(int i = 0; i < arr.length - 1; i++){
            int minIndex = i;
            for(int j = i + 1; j < arr.length; j++){
                if(arr[j] < arr[minIndex]){
                    minIndex = j;
                }
            }

            if (i != minIndex) {
                // 将找到的最小值与当前位置i交换
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }
    }

    /**
     * 优化：双向选择排序
     * 双向选择排序是选择排序的一种变体，每轮同时选出最小值和最大值，分别放到序列的两端：
     * @param args
     */
    public static void bidirectionalSelectionSort(int[] arr) {
        int left = 0;
        int right = arr.length - 1;

        while (left < right) {
            int minIndex = left;
            int maxIndex = left;

            // 在当前未排序区间找出最小值和最大值的索引
            for (int i = left + 1; i <= right; i++) {
                if (arr[i] < arr[minIndex]) {
                    minIndex = i;
                }
                if (arr[i] > arr[maxIndex]) {
                    maxIndex = i;
                }
            }

            // 将最小值交换到左边
            if (minIndex != left) {
                int temp = arr[left];
                arr[left] = arr[minIndex];
                arr[minIndex] = temp;

                // 如果最大值的索引恰好是left，交换后最大值现在在minIndex位置
                if (maxIndex == left) {
                    maxIndex = minIndex;
                }
            }

            // 将最大值交换到右边
            if (maxIndex != right) {
                int temp = arr[right];
                arr[right] = arr[maxIndex];
                arr[maxIndex] = temp;
            }

            left++;
            right--;
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 4, 3, 2, 1};
        selectionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
